#include <bits/stdc++.h>
using namespace std;

/*
3335. 字符串转换后的长度 I
已解答
中等
相关标签
相关企业
提示
给你一个字符串 s 和一个整数 t，表示要执行的 转换 次数。每次 转换 需要根据以下规则替换字符串 s 中的每个字符：

如果字符是 'z'，则将其替换为字符串 "ab"。
否则，将其替换为字母表中的下一个字符。例如，'a' 替换为 'b'，'b' 替换为 'c'，依此类推。
返回 恰好 执行 t 次转换后得到的字符串的 长度。

由于答案可能非常大，返回其对 109 + 7 取余的结果。

 

示例 1：

输入： s = "abcyy", t = 2

输出： 7

解释：

第一次转换 (t = 1)
'a' 变为 'b'
'b' 变为 'c'
'c' 变为 'd'
'y' 变为 'z'
'y' 变为 'z'
第一次转换后的字符串为："bcdzz"
第二次转换 (t = 2)
'b' 变为 'c'
'c' 变为 'd'
'd' 变为 'e'
'z' 变为 "ab"
'z' 变为 "ab"
第二次转换后的字符串为："cdeabab"
最终字符串长度：字符串为 "cdeabab"，长度为 7 个字符。
示例 2：

输入： s = "azbk", t = 1

输出： 5

解释：

第一次转换 (t = 1)
'a' 变为 'b'
'z' 变为 "ab"
'b' 变为 'c'
'k' 变为 'l'
第一次转换后的字符串为："babcl"
最终字符串长度：字符串为 "babcl"，长度为 5 个字符。
 

提示：

1 <= s.length <= 105
s 仅由小写英文字母组成。
1 <= t <= 105
*/

// 法一
class Solution {
public:
    using ll = long long;
    int lengthAfterTransformations(string s, int t) {
        const int MOD = 1e9 + 7;
        vector<ll> count(26, 0);
        for (char ch : s)
            count[ch - 'a']++;
        for (int i = 0; i < t; i++) {
            ll z_count = count[25];
            for (int j = 25; j >= 1; j--) {
                // 向后移动
                count[j] = count[j - 1];
            }
            // 转换
            count[0] = z_count;
            count[1] += z_count;
            count[1] %= MOD;
        }
        ll total = 0;
        for (int i = 0; i < 26; ++i) {
            total += count[i];
            total %= MOD;
        }
        return total;
    }
};

// 法二
class Solution {
public:
    int lengthAfterTransformations(string s, int t) {
        int mod = 1000000007; // 定义模数，用于防止结果溢出
        long cnt[26]{}; // 初始化一个长度为26的数组，用于统计每个字母的出现次数（'a'到'z'）
        int ans = 0; // 初始化最终结果变量，表示字符串的总长度

        // 遍历输入字符串s，统计每个字符的出现次数，并初始化ans为字符串的初始长度
        for(auto& a : s){
            ans++;
            cnt[a - 'a']++; // 将字符转换为对应的索引（'a'->0, 'b'->1, ..., 'z'->25）
        }

        // 执行t次转换
        for(int i = 25, j = 0; t > 0; t--, i--, j--){
            // 处理索引越界的情况，循环到字母表的开头
            if(j < 0) j = 25;
            if(i < 0) i = 25;

            // 根据转换规则更新字符数量：
            // 1. 当前字符i（从'z'开始逆序处理）会被转换为下一个字符j（i的下一个字符）
            // 2. 如果是'z'（i=25），则会被替换为"ab"，即增加一个字符（'a'和'b'各增加cnt[i]次）
            cnt[j] += cnt[i] % mod; // 更新字符j的数量，并取模防止溢出
            ans = (ans + cnt[i]) % mod; // 更新总长度，并取模防止溢出
        }

        return ans; // 返回最终结果
    }
};